Conventionally, upon managing secret information in an information processing apparatus such as a computer or the like, secret information may leak to a third party due to inadequate information management or intentional act of an administrator, and this poses a serious problem in a recent information processing environment in which a plurality of information processing apparatuses are connected via a communication network.
Hence, a scheme of sharing and distributing secret information to be managed among a plurality of members who form a given group in place of a specific person who manages secret information, and reconstructing (restoring) and using original secret information based on the shared and distributed information pieces only when that secret information is required has been proposed. This scheme is called a secret sharing scheme.
In the aforementioned secret sharing scheme, even when not all pieces of shared information distributed to the members of the group are available, it is possible to allow reconstructing original secret information. That is, in the conventional secret sharing scheme, even when some pieces of distributed shared information outflow, the entire secret information to be managed does not leak depending on the outflowed pieces of shared information. Also, even when some pieces of shared information are destroyed, original secret information can be reconstructed on the basis of the remaining pieces of shared information.
A (k, n)-threshold secret sharing scheme as an example of the secret sharing scheme having such feature encodes secret information S into n pieces of shared information W_i (1≦i≦n). In this scheme, it is possible to reconstruct secret information S from arbitrary k (k≦n) pieces of shared information, but it is impossible to obtain any information that relates to the secret information S from (k−1) or less pieces of shared information. Note that this scheme is proposed by A. Shamir “How to Share a Secret”, Commun. of ACM, Vol. 22, No. 11, pp. 612-613, 1979, or Tatsuaki Okamoto and Hiroshi Yamamoto, “Modern Cryptography”, Sangyo Tosho, pp. 209-219.
As a new type of such secret sharing scheme, a visual secret sharing scheme has also been proposed. In this scheme, images are used as secret information and shared information, and no mathematical operation is made upon reconstructing images as secret information.
As an example of such visual secret sharing scheme, a visual secret sharing scheme based on the (k, n)-threshold secret sharing scheme is proposed first by M. Naor and A. Shamir, Visual Cryptography (in Advances in Cryptology—Eurocrypt '94, Lecture Notes in Computer Science 950, pp. 1-12, Springer-Verlag). In this scheme, upon sharing a secret image as secret information to be managed in the form of a plurality of shared images, individual shared images are printed on media such as opaque slide films, OHP (overhead projector) sheets, or the like, which have transparency and can be physically stacked up (overlaid on) each other. Upon reconstructing an original secret image, the individual shared images need only be stacked up each other. In this way, the secret image can be reconstructed without any special cryptographic operations.
A practical visual secret sharing scheme based on the (k, n)-threshold secret sharing scheme will be explained below.
This method provides a mechanism in which n shared images are generated in advance from one secret image, and an original secret image can be reconstructed by stacking up k or more shared images, but information that relates to the secret image cannot be acquired even by stacking up (k−1) or less shared images. A secret image SI is a monochrome (binary) image, and each component SI(x, y) which forms that image is expressed by “0” if the pixel is white or “1” if the pixel is black.
In this case, each pixel which forms the secret image SI is expressed by m partial pixels on n shared images (that is, a partial pixel is expanded to m times that in the secret image). When a plurality of shared images are stacked up each other, white or black is visually reconstructed by the difference (i.e., contrast) between the white and black ratios of m partial pixels, thus obtaining an original secret image.
The forming method of shared images in the visual secret sharing scheme is as follows.
A basis matrix will be explained first. Each shared image is shared based on a basis matrix. Two different basis matrices are used upon forming shared images from a secret image. A basis matrix S0 is used when the pixel component of the secret image is 0, and a basis matrix S1 is used when the pixel component of the secret image is 1. Each basis matrix is an n×m matrix, and the rows of this matrix are indexed by a vertex set {u_i|1≦i≦n}.
These basis matrices are prepared to have the following features for a given threshold value d (1≦d≦n).
(1) The basis matrices S0 and S1 are binary matrices.
(2) For i that falls within the range 1≦i≦n, the weight (the number of components “1”) of the (u_i)-th row component of the basis matrix S0 equals to that of the (u_i)-th row component of the basis matrix S1.
(3) The Hamming distance (i.e., the number of “1”s of vectors) of the vector obtained by selecting arbitrary k different row vectors of the basis matrix S0 and ORing the selected row vectors is less than d.
(4) The Hamming distance of the vector obtained by selecting arbitrary k different row vectors of the basis matrix S1 and ORing the selected row vectors is equal to or larger than d.
(5) For all “q”s which fall within the range 1≦q<k, the Hamming distance of the vector obtained by selecting arbitrary q different row vectors of the basis matrix S0 and ORing the selected row vectors equals to the Hamming distance of the vector obtained by selecting arbitrary q different row vectors of the basis matrix S1 and ORing the selected row vectors.
To generate shared images, each component SI(x, y) of the externally input secret image SI undergoes the following processes.
(1) The basis matrix S0 is selected if SI(x, y) is 0 or Si if SI(x, y) is 1.
(2) An arbitrary permutation Φ is selected from an m-th order permutation group.
(3) An (x, y) component of each shared image w_i (1≦i≦n) before sharing is set to be a value obtained by applying the permutation Φ the (u_i)-th row component (vector of m variables) of the basis matrix.
With these processes, shared images w_i (1≦i≦n) expanded to m times are generated, thus providing a mechanism in which the original secret image SI can be reconstructed by stacking up k or more shared images, but the secret image SI cannot be obtained by stacking up (k−1) or less shared images.
FIG. 11 exemplifies basis matrices S0 and S1 (m=4) related to on a (2, 2)-threshold visual secret sharing scheme as an example of the conventional visual secret sharing scheme based on the (k, n)-threshold value secret sharing scheme.
FIG. 12 shows an example of shared images formed based on the basis matrices exemplified in FIG. 11. In FIG. 12, a secret image 1203 is reconstructed by stacking up shared images 1201 and 1202.
In the conventional visual secret sharing scheme based on the (k, n)-threshold value secret sharing scheme, information pieces which form a secret image are equally distributed to shared images. However, in various activities in the real world, a permission of a specific member is required upon reconstructing secret information to be managed, or reconstructing is not permitted to a specific member constitution. In this way, various access structures (constraint conditions) may have to be imposed upon reconstructing secret information. For this reason, the scheme of equally distributing shared images to a plurality of members is not often suitable.